package com.cuz.for2024;

import java.lang.reflect.Array;
import java.util.Arrays;

public class T983 {

    public static void main(String[] args) {
        int[] days = new int[]{1, 4, 6, 7, 8, 20};
        int[] costs = {2, 7, 15};
        System.out.println(new T983().mincostTickets1(days, costs));
        System.out.println(new T983().mincostTickets2(days, costs));
    }

    private static final int[] durations = new int[]{1, 7, 30};

    public int mincostTickets2(int[] days, int[] costs) {
        if (days == null || days.length == 0) {
            return 0;
        }
        int[] dp = new int[days.length + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[days.length] = 0;
        // dp[i]从days[i]开始 到 最后一天的花费

        for (int i = days.length - 1; i >= 0; i--) {
            int j = i;

            for (int k = 0; k < 3; k++) {

                while (j < days.length
                        && days[i] + durations[k] > days[j]) {
                    j++;
                }

                dp[i] = Math.min(dp[i], dp[j] + costs[k]);
            }
        }
        return dp[0];
    }

    public int mincostTickets1(int[] days, int[] costs) {
        if (days == null || days.length == 0) {
            return 0;
        }
        int[] cached = new int[days.length];
        Arrays.fill(cached, -1);
        return process(days, costs, 0, cached);
    }

    private int process(int[] days, int[] costs, int i, int[] cached) {
        if (i >= days.length) {
            return 0;
        }
        if (cached[i] != -1) {
            return cached[i];
        }
        int ans = Integer.MAX_VALUE;
        // 方案
        for (int k = 0, j = i; k < 3; k++) {
            while (j < days.length
                    && days[i] + durations[k] > days[j]) {
                j++;
            }

            ans = Math.min(ans, costs[k] + process(days, costs, j, cached));
        }
        cached[i] = ans;
        return ans;
    }
}
